package com.zhaopin.theswordreferstooffer;

import java.util.Arrays;

/**
 * @author yin.peide
 * @date 2021-06-23 16:34
 * <p>
 * 回头自己整理 插入排序，冒泡排序，归并排序，快速排序
 */
public class Offer1Sort {

    public static int[] attr = {5, 2, 23, 8, 43, 1, 9};

    public static void main(String[] args) {
//        int[] sortedAttr = bubble(attr);
//        for (int i : sortedAttr) {
//            System.out.print(i + " ");
//        }
//        System.out.println();
//
        int[] sortedAttr1 = insertSort(attr);
        for (int i : sortedAttr1) {
            System.out.print(i + " ");
        }
        System.out.println();
//

//        quickSort(attr,0,attr.length-1);
//        for (int i : attr) {
//            System.out.print(i + " ");
//        }
//        System.out.println();
    }

    /**
     * 手写冒泡
     *
     * @param attr
     * @return
     */
    public static int[] bubble(int[] attr) {

        for (int i = 0; i < attr.length - 1; i++) {
            for (int j = i + 1; j < attr.length; j++) {
                // 拿到 attr[i] 与 attr[j] 做比较
                int temp1 = attr[i];
                int temp2 = attr[j];
                if (temp1 > temp2) {
                    attr[i] = temp2;
                    attr[j] = temp1;
                }
            }
        }

        return attr;
    }

    /**
     * 手写插入排序
     *
     * @return
     */
    public static int[] insertSort(int[] attr) {

        for (int i = 1; i < attr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (attr[j] < attr[j - 1]) {
                    int temp1 = attr[j];
                    int temp2 = attr[j - 1];
                    attr[j - 1] = temp1;
                    attr[j] = temp2;

                }
            }
        }
        return attr;
    }


    /**
     * 归并排序
     *
     * @param attr
     * @return
     */
    public static int[] mergerSort(int[] attr) {
        return null;
    }

    /**
     * 快速排序
     *
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static void quickSort(int[] arr, int low, int high) {

        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);

            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            //quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }

    }

    private static int getIndex(int[] arr, int low, int high) {
        // 基准数据
        int tmp = arr[low];
        while (low < high) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            arr[low] = arr[high];
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            arr[high] = arr[low];

        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
        arr[low] = tmp;
        return low; // 返回tmp的正确位置
    }
}

